package gold.digger;


import gold.vo.TreeNode;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC105 {



    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeRecur(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode buildTreeRecur(int[] preorder, int[] inorder,
                                   int preOrderStart, int preOrderEnd,
                                   int inOrderStart, int inOrderEnd) {
        if (preOrderStart > preOrderEnd || inOrderStart > inOrderEnd ||
                preOrderStart < 0 || preOrderEnd > inorder.length - 1 ||
                inOrderStart < 0 || inOrderEnd > inorder.length - 1) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preOrderStart]);
        int rootPos = findPos(inorder, preorder[preOrderStart]);
        root.left = buildTreeRecur(preorder, inorder, preOrderStart + 1, preOrderStart + (rootPos - inOrderStart), inOrderStart, rootPos - 1);
        root.right = buildTreeRecur(preorder, inorder, preOrderStart + (rootPos - inOrderStart) + 1, preOrderEnd, rootPos + 1, inOrderEnd);
        return root;
    }

    public int findPos(int[] order, int targetNum) {
        for (int i = 0; i < order.length; i++) {
            if (order[i] == targetNum) {
                return i;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        LC105 an = new LC105();
//        int[] preorder = {3, 9, 20, 15, 7};
//        int[] inorder = {9, 3, 15, 20, 7};
        int[] preorder = {1, 2, 4, 5, 3, 6, 8, 7, 9};
        int[] inorder = {4, 2, 5, 1, 8, 6, 3, 7, 9};
        System.out.println(an.buildTree(preorder, inorder));
    }
}
